package com.kehao.leetcode.middle.backtracking_algorithm;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesisSolution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        char[] temp = new char[n*2];
        int leftRemain = 0;
        int leftCount = 0;

        fillResult(0,temp,result,leftRemain,leftCount);

        return result;
    }

    private void fillResult(int i, char[] temp, List<String> result, int leftRemain, int leftCount) {
        if(i==temp.length){
            result.add(new String(temp));
        }else {
            if(leftCount<temp.length/2){
                if(leftRemain>0){
                    temp[i] = '(';
                    fillResult(i+1,temp,result,leftRemain+1,leftCount+1);
                    temp[i] = ')';
                    fillResult(i+1,temp,result,leftRemain-1,leftCount);
                }else {
                    temp[i] = '(';
                    fillResult(i+1,temp,result,leftRemain+1,leftCount+1);
                }
            }else {
                temp[i] = ')';
                fillResult(i+1,temp,result,leftRemain-1,leftCount);
            }
        }
    }


    @Test
    public void test01(){
        System.out.println(generateParenthesis(3));
    }
}